package algorithm.poj.p3000;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLDecoder;


/**
 * 分析：
 * 因为结果一定是整数，我们可以采用二分法获得最大月费用的最小值
 * 
 * 经验：
 * 
 * 教训：
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P3273 {

	public static void main(String[] args) throws Exception {

		InputStream input = null;
		if (false) {
			input = System.in;
		} else {
			URL url = P3273.class.getResource("P3273.txt");
			File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
			input = new FileInputStream(file);
		}
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(input));

		String line = stdin.readLine();
		String[] tmp = line.split("\\s+");
		int N = Integer.valueOf(tmp[0]);
		int M = Integer.valueOf(tmp[1]);
		int[] d = new int[N];
		for (int i = 0; i < N; i ++) {
			line = stdin.readLine().trim();
			d[i] = Integer.valueOf(line);
		}
		System.out.println(minmax(d, M));
	}

	private static int minmax(int[] d, int M) {
		
		int sum = 0;
		for (int i = 0; i < d.length; i ++) sum += d[i];
		
		int l = 0;
		for (int i = 0; i < d.length; i ++) if (l < d[i]) l = d[i];
		l --;
		
		int r = sum;
		while (r - l > 1) {
			int m = (l + r)/2;
			//check
			int count = 1;
			int s = 0;
			for (int i = 0; i < d.length; i ++) {
				if (s + d[i] <= m) {
					s += d[i];
					continue;
				} else {
					s = d[i];
					count ++;
				}
			}
			if (count <= M) {
				r = m;
			} else {
				l = m;
			}
		}
		return r;
	}
}
